public class Hanoi {
    //青蛙跳台阶
    public static int jump(int n) {
        if(n==1) {//第一次跳一个台阶
            return 1;
        }else if(n==2) {//2个台阶时一次跳一个或一次跳2个
            return 2;
        }else {
            //第一次跳一个则后面有n-1种跳法，第一次跳2个台阶后面有n-2个跳法
            int sum = jump(n-1)+jump(n-2);
            return sum;
        }
    }
    public static void main(String[] args) {
        System.out.println(jump(4));//台阶数
    }


                    //表示把盘子从一个位置移到另一个位置
    public static void move(char p1,char p2) {
        System.out.print(p1+"->"+p2+"  ");
    }

                                  //起始位置，中转位置，目的地
    public static void hanoi(int num,char pos1,char pos2,char pos3) {
        if(num==1) {
            move(pos1,pos3);
        }else {
            //把上面num-1个盘子借助位置三，放到位置二
            hanoi(num-1,pos1,pos3,pos2);
            //再把剩余的一个盘子放到位置三
            move(pos1,pos3);
            //再把位置二上面num-1个盘子借助位置1放到位置三
            hanoi(num-1,pos2,pos1,pos3);
        }
    }
    //汉诺塔
    public static void main1(String[] args) {

        hanoi(3,'A','B','C');
    }
}
